1. Field of the Invention
The invention relates to apparatus, as well as to accompanying methods for use therein, for illustratively implementing a large (e.g. approximately 1 Terabit/second) packet switch or a non-buffer based statistical multiplexor, using a crossbar matrix network in which, first, the output ports of the individual switching elements are partitioned into various groups in order to share routing paths among the elements in any such group and, second, the outputs of each such group are themselves recursively partitioned into a succession of serially connected groups that each provides a decreasing number of outputs until one such output is provided for each corresponding output port of the switch. Such a switch also utilizes channel grouping to improve overall performance and a crossbar, e.g., crosspoint matrix, switching fabric that internally distributes contention resolution and filtering functions among the individual switching elements themselves to reduce complexity, provide modularity, reduce growth limitations and relax synchronization requirements of the entire switch.
2. Description of the Prior Art
Presently, the growing deployment of the public integrated services digital network (ISDN) throughout the nationwide telephone system permits each ISDN subscriber to gain access to a communication channel that possesses a significantly increased bandwidth over that available through a conventional telephone (i.e. POTS--plain old telephone service) connection. Although the bandwidth provided by basic rate ISDN service has the potential to provide a wide variety of new communication services to each of its subscribers, in the coming years various communication technologies that are just now emerging, such as broadband video and very high speed data transmission, are expected to impose bandwidth requirements on subscriber ISDN channels that will far exceed the bandwidth obtainable at a basic rate ISDN interface. Such an interface consists of two 64 kbit/second "B" channels and one 16 kbit/second "D" channel, where the "D" channel is a packet channel which carries signalling information for communication occurring over each B channel.
For example, broadband video service offerings might include: desktop teleconferencing having voice/video/data communication from a single terminal located at one's desk, distribution video, video-on-demand, videotelephone, still video picture services and high definition television. In terms of bandwidth, just one high definition television signal is expected to require, depending upon the manner in which it is encoded, at least 45 Mbit/second of channel bandwidth. Clearly, the bandwidth of such a signal far exceeds that furnished by a basic rate ISDN channel.
In an effort to provide sufficient channel bandwidth to meet expected subscriber demand in a public ISDN environment, the art has turned to implementing so-called broadband ISDN (B-ISDN). In B-ISDN, each subscriber channel is presently envisioned as providing an information transfer capacity of approximately 150 Mbit/second. This rate is chosen to provide a minimally sufficient bandwidth at a subscriber interface to simultaneously carry a broadband video service, such as high definition video, and various narrowband services, such as voice transmission. In addition, B-ISDN is also expected to serve as a high speed data transport facility for interconnecting separate local area networks (LANs). Presently, Ethernet based and many other types of LANs generally operate at a gross bit rate of approximately 10 Mbit/second. A proposed LAN, the Fiber Distributed Data Interface, is expected to operate at a gross bit rate of 125 Mbit/second. With this in mind, a bandwidth of 150 Mbit/second currently appears to be sufficiently fast to satisfactorily interconnect a wide variety of different LANs, encompassing those that are currently in use to many of those that are presently being proposed. Furthermore, B-ISDN must also fully accommodate relatively slow ISDN traffic, such as that which occurs at the basic rate.
ISDN involves a marriage of two different transport and switching technologies: circuit switching and packet switching. Circuit switching inherently involves continuously maintaining a real time communication channel at the full channel bandwidth between two points in order to continuously carry information therebetween throughout the duration of a call. Owing to this inherent characteristic, circuit switching can not efficiently accommodate bursty traffic and, for this reason, is generally viewed in the art as being ill suited for use in B-ISDN. Specifically, communication for many services that will occur at relatively low information transfer rates in a B-ISDN environment will appear as periodic bursts when transported over a B-ISDN subscriber channel. In addition, high speed data, such as that occurring over a LAN interconnection, will itself be bursty even apart from the channel. Bursty communications do not require full channel bandwidth at all times. Whenever a circuit switched connection is used to carry bursty traffic, available communication bandwidth that is dedicated to carrying data that occurs between successive bursts, i.e. whenever there is no information to be transferred, is simply wasted. Inasmuch as bursty communications, of one sort or another, are expected to constitute a significant portion of B-ISDN traffic, the significant inefficiencies that would otherwise result from using circuit switched connections to carry bursty traffic through a communication channel generally dictate against using circuit switched connections in a B-ISDN environment.
Despite the inherent limitation on carrying bursty traffic at high efficiencies over circuit switched connections, attempts are still being made in the art to adapt circuit switching to a B-ISDN environment. Nevertheless, while many advances have been and are continuing to be made in circuit switching technology, circuit switching still remains poorly adapted to supporting communication services that occur over widely diverse information transfer rates, such as those which are expected to occur in B-ISDN. For example, one attempt advocates overlaying a number of circuit switching fabrics to form a network, with each different fabric operating at a transfer rate of a single prominent broad- or narrowband service. Unfortunately, if this attempt were to be implemented, then segregated switching fabrics would likely proliferate throughout the public telephone network which would disadvantageously and unnecessarily complicate the tasks of provisioning, maintaining and operating the network. Hence, this attempt is not favored in the art. Another attempt in the art aims at providing multi-rate switching. Here, a single group of allocated channels would provide information transport, with each channel providing information transport at a different multiple of a basic transfer rate. A switch would then be dynamically reconfigured, based upon each subscriber' s needs, to support specific services therefor that occur at different transfer rates. Unfortunately and disadvantageously, the resulting switch would be considerably more complex than a single rate circuit switch. Furthermore, all channels in a group would need to be synchronized with respect to each other and with no differential delay occurring thereamong. Owing to the need from time to time to switch calls from one physical facility to another as required by network maintenance, maintaining the necessary intra-group synchronization is likely to be quite difficult. As such, this proposal is also not favored. In this regard, see, H. Ahmadi et al, "A Survey of Modern High-Performance Switching Techniques", IEEE Journal on Selected Areas in Communications, Vol. 7, No. 7, September 1989, pages 1091-1103 (hereinafter referred to as the Ahmadi et al publication); and J. J. Kulzer et al, "Statistical Switching Architectures for Future Services", International Switching Symposium ISS'84, Florence, Italy, May 7-11, 1984, Session 43A, paper 1, pages 1-5 (hereinafter referred to as the Kulzer et al publication).
Given the drawbacks associated with circuit switched connections, packet switched connections, specifically using asynchronous transfer mode (ATM), presently appear to be the preferred mode of communication over B-ISDN. This mode involves asynchronous time division multiplexing and fast (high speed) packet switching. In essence, ATM relies on asynchronously transporting information in the form of specialized packets, i.e. so-called ATM "cells". Each ATM cell includes a header followed by accompanying data. The header contains a label, which is used for multiplexing and routing, that uniquely identifies the B-ISDN channel which is to carry that cell between two network nodes. A specific periodic time slot is not assigned to carry a cell on any B-ISDN channel. Rather, once an ATM cell reaches, for example, a B-ISDN switch, fast packet switching occurs: a route is dynamically established through the switch to an output destination for that particular cell followed by transport of the cell over that route, and so on for each successive cell. A route is only established in response to the cell reaching an input of the switch.
Advantageously, ATM communication allows any arbitrary information transfer rate up to the full facility rate to be supported for a B-ISDN service by simply transmitting cells at a corresponding frequency into the network. With ATM, channel bandwidth is dynamically allocated to any B-ISDN call and simply varies with the rate at which cells for that call are applied through a B-ISDN channel. No further intervention is required by either the subscriber or the network itself to utilize differing amounts of available channel bandwidth as the need therefor arises. Any change in that subscriber's traffic patterns or services, even if dramatic, merely results in a changing mix of cells that are presented to the network for these services and changes in their corresponding rates of occurrence. As long as sufficient bandwidth is available on any subscriber channel to carry all the cells presented thereto, the ATM switching fabric merely continues to route cells to their appropriate destinations and remains essentially unaffected by any such change. Hence, by decoupling the information transfer rates from the physical characteristics of the switching fabric and providing the capability to handle bursty traffic, ATM is particularly well suited to transporting both bursty and continuous bit rate services and is therefore preferred for B-ISDN service. In this regard, see the Kulzer et al publication.
An essential ingredient of B-ISDN is an ATM switch. In order to support B-ISDN, that switch needs to possess the capability of routing cells at an information transfer rate of at least 150 Mbit/second between separate ATM ports. Based upon current estimates, a large central office B-ISDN switch is expected to handle approximately 80,000 subscriber lines each having a 150 Mbit/second channel. With a concentration ratio of 10 to 1, the switch needs to possess a total throughput of approximately 1.2 Terabit/second (1.2.times.10.sup.12 bits/second).
Crossbar based switch architectures have received a great deal of attention in the art. The reason for this is simple: crossbar switches have historically proven to be very reliable under actual service conditions and, are internally non-blocking, i.e. once appropriate connections are established through a cross bar matrix at any given time there will be no contention for any link residing within that matrix and thereby two cells will not collide within the matrix. See, e.g. U.S. Pat. No. 4,692,917 (issued to M. Fujoika on Sep. 8, 1987). Crossbar switches also possess the capability of being able to dynamically isolate a number of separate switching elements from active service without significantly affecting the throughput of the entire switch. However, crossbar switches possess several drawbacks which must be adequately addressed in any switch design. First, crossbar switches suffer from output port contention, i.e. two or more packets attempting to simultaneously appear at the same output port. Due to the non-deterministic (random) nature of packet arrival times and destinations, contention can occur in any packet switch architecture. Second and more significantly, crossbar type switches tend to contain a very substantial number of crosspoint elements and interconnects. In particular, since each of N inputs is connected to each of N outputs, a crossbar matrix contains N.sup.2 crosspoint elements and interconnections. Inasmuch as a 1 Terabit/second switch for B-ISDN service is expected to service approximately 6000-8000 (or more) input ports, this necessitates that a crossbar matrix for use in such a switch must contain approximately 36-64 Million (or more) separate crosspoints and a similar number of interconnections. Such a large number of crosspoints and interconnections is not only very complex to implement but also inordinately costly. Furthermore, crossbar based switches frequently rely on using centralized circuitry to control routing and perform contention resolution. Use of such circuitry further complicates the interconnect wiring owing to the additional wiring needed to connect the centralized circuitry to and from each individual switching element. This added complexity may rival or even exceed that required within the crossbar matrix itself. As such and principally because of the resulting cost and complexity, the art teaches that a single stage crosspoint matrix should be used only in those instances where the packet switch is relatively small or where a relatively small crosspoint matrix forms a building block of a large multi-stage switch. In this regard, see pages 1098 and 1099 of the Ahmadi et al publication as well as pages 4 and 5 of the Kulzer et al publication.
Nevertheless, owing to the advantages inherent in crossbar based switches which are not present or readily attainable in other well-known switch architectures, such as Batcher-Banyan and other designs that rely on cascaded routing networks, significant work has been undertaken in the art to modify a crossbar matrix in an effort to ameliorate the disadvantages heretofore associated with using a crossbar matrix in a large packet switch.
Output port contention can be remedied by incorporating a queue, specifically buffers, in one or more locations in the switch to store one (or more) contending packets for an output port while another contending packet is routed through that port. For a crossbar switch, a buffer(s) can be placed at the input ports, at the output ports or within each crosspoint element itself. Use of such a buffer along with associated centralized control circuitry can, depending upon the location of the buffer(s), significantly increase the cost and complexity of the switch. In this regard, buffer placement and size tend to be critical issues in switch design. Increasing the number of buffers generally increases the throughput of the switch, i.e. the load that can be carried before packets are lost, but at the expense of added hardware and associated delay in transporting packets through the switch. The art teaches that, in resolving contention, output port buffering provides the highest switch throughput as compared to the input or crosspoint based buffering and is therefore the favored approach. In this regard, see page 1096 of the Ahmadi et al publication.
With this in mind, the art has recently proposed a crossbar based architecture for a large, high speed, e.g. approximately 1 Terabit/second, packet switch, such as that suited for ATM service, which incorporates output buffering. This architecture, which is referred to as the so-called "Knockout" switch and is currently receiving relatively wide attention in the art, is aimed at reducing the number of interconnections occurring between all the switching elements and a centralized controller and hence some of the cost and complexity associated with implementing a large packet switch from a large crossbar matrix as well as providing increased delay/throughput performance. See, for example, Y. Yeh et al, "The Knockout Switch: A Simple, Modular Architecture for High-Performance Packet Switching", IEEE Journal on Selected Areas in Communications, Vol. SAC-5, No. 8, October 1987, pages 1274-1283; and H. Ahmadi et al, "A Survey of Modern High-Performance Switching Techniques", IEEE Journal on Selected Areas in Communications, Vol. 7, No. 7, September 1989, pages 1091-1103. In essence, a Knockout switch contains a separate input line for each input; with N such inputs, the switch contains N such lines as well as N separate routing paths extending therefrom to each of N associated interfaces. Incoming packets on any one input are broadcast over the corresponding input line to all N routing paths connected to that line. Each such interface contains N packet filters, an N-to-L concentrator (where the value of N is substantially greater than the value of L) and a shifter and shared buffer. Each packet filter is connected to a different one of the N input lines. The outputs of each packet filter feeds the concentrator which, in turn, feeds the shifter and shared buffer. Operationally speaking, each of the packet filters receives incoming packets from a particular input line and examines the routing header in each of these packets. Within any one output port, the packet filter routes only those packets, which possess a routing address that matches the address for the particular output port, onward on to an input of the concentrator. In this manner, the packet filters provide a self-routing function. The concentrator then selects L packets from its N incoming lines. The L packets are stored in their order of arrival in the shared buffer. Stored packets are then shifted out of the shared buffer in seriatim and applied to an appropriate output interface module which, in turn, applies the packets to an output port of the switch. If more than L packets are simultaneously routed through the packet filters to the concentrator, the concentrator simply drops out, i.e. knocks out, all the excess packets therefrom. Owing to the error detection and correction capabilities (including packet re-transmission) inherent in a packet, particularly ATM, network, a relatively small amount of cell loss can be readily tolerated. Due to the natural randomness of the arriving cells, the art has specifically observed that if the value of L is sufficiently large, then the probability of L simultaneously occurring packets being routed to the same output port in one ATM cell time interval is very small. For example, if L is set to twelve, and assuming uncorrelated packet traffic occurs among the input ports with uniform packet distribution by the concentrator, then the probability that more than 12 ATM cells will be destined to at any one output port during a single ATM cell time interval becomes approximately 10.sup.-10 Inasmuch as the expected cell loss of an optical fiber link and associated circuitry is expected to be on the order of 10.sup.-9, the cell loss inherent in the knockout switch is acceptable and, for non-real time services, can be readily compensated by appropriate re-transmission of "knocked out" cells. Since cell knockout and concentration of remaining cells effectively resolve contention within any one output port, a knockout based switch does not need a centralized circuit to resolve contention. Moreover, since all the bus interfaces in such a switch collectively implement a self-routing function, a centralized circuit to control routing is not needed either. While the elimination of such a centralized control circuit significantly reduces the interconnect wiring by eradicating the wiring heretofore required by that circuit, a substantial number of interconnects still remains. In this regard, as discussed above, each interface in a knockout switch is connected to every one of the N input lines thereby necessitating for an N line switch, N.sup.2 separate interconnections. For a large switch (e.g. N=approximately 8000), a large number of interconnections is still quite complex and costly to implement.
Thus, a need exists in the art for a large, e.g. at least 1 Terabit/second, packet switch particularly suited for use with ATM communication that utilizes the knockout principle but with a markedly reduced number of interconnections within the switch fabric over that required by conventional knockout switches known in the art.